`
https://leetcode.cn/problems/course-schedule-ii/
`

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  // 将依赖关系转换为图结构
  const graph = buildGraph(numCourses, prerequisites)

  // 构建入度数组
  const indegree = new Array(numCourses).fill(0)
  for (const edge of prerequisites) {
    const to = edge[0]
    indegree[to]++
  }

  // 构建队列，把入度为 0 的节点都作为遍历起始点
  const q = []
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) {
      q.push(i)
    }
  }

  // 记录拓扑排序结果
  const res = new Array(numCourses).fill(0)
  // 记录遍历节点的顺序（索引）
  let count = 0

  while (q.length) {
    // 弹出节点 cur，并将它指向的节点的入度减一
    const cur = q.shift()
    // 弹出节点的顺序即为拓扑排序结果
    res[count] = cur
    count++
    for (const next of graph[cur]) {
      indegree[next]--
      if (indegree[next] === 0) {
        // 如果入度变为 0，说明 next 依赖的节点都已被遍历
        q.push(next)
      }
    }
  }

  if (count != numCourses) {
    // 存在环，拓扑排序不存在
    return []
  }

  return res

};

function buildGraph(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(null).map(() => [])
  for (const edge of prerequisites) {
    const from = edge[1], to = edge[0]
    graph[from].push(to)
  }
  return graph
}

// test
console.log(findOrder(2, [[1, 0]])) // [0, 1]
console.log(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) // [0, 1, 2, 3]
console.log(findOrder(1, [])) // [0]